\documentclass[a4paper]{article}
\usepackage[UTF8]{ctex}
\usepackage{listings}
\lstset{numbers=left,
	basicstyle=\ttfamily,
	language=c++}

	\title{作业二: bst排序算法的实现}

	\author{韩李玮\\ 统计学 3210104658}

	\date{\today}

\begin{document}
	
	\maketitle
	
\section{创建要求}
			
编写BSTsorting函数实现对数组的排序。必须使用二叉搜索树排序算法。有两种不同的模式，一种乱序后排序一种不乱序直接排序，同时需要测试不乱序时的最坏效率和乱序后的平均效率。

\section{设计思路}
1.阅读头文件，添加注释。\par
2.为了实现排序，需要先将数据转移走并清空原数组，排序完成后将数据重新存入数组。\par
3.在头文件中编写add函数，实现将BinarySearchTree中的数据添加至数组。\par
4.进行测试程序编写。\par
5.编写外部函数BSTSorting，同时测试其效率。\par
6.最后编写main函数对头文件进行测试。\par
7.进行脚本文件编写

\section{在书本基础上添加的函数}
1.BinarySearchTree类对其私有add方法的调用
\begin{lstlisting}
	void add(std::vector<Comparable> &arr) const
	{
		if( isEmpty( ) )
		std::cout << "Empty tree" << std::endl;
		else
		add( root,arr );
	}
\end{lstlisting}
2.BinarySearchTree类私有的add方法
\begin{lstlisting}
	void add(BinaryNode *t ,std::vector<Comparable> &arr) const
	{
		if(t != nullptr )
		{
			add( t->left,arr );
			arr.push_back(t->element);
			add( t->right,arr );
		}
	}
\end{lstlisting}
3.BSTsorting模板函数
\begin{lstlisting}
	template <typename Comparable>
	void BSTSorting(std::vector<Comparable> &_arr, int _mode = 0)
	{
		int start,finish;
		BinarySearchTree<Comparable> bst{};
		if (_mode == 0)
		{
			start=clock();
			for(int times = 0 ;times < 5;times++)
			{
				for(int i = 0;i < _arr.size();i++)
				{
					bst.insert(_arr[i]);
				}
				_arr.clear();
				bst.add(_arr);
			}
			finish=clock();
			std::cout << "The sorting process costs " << (finish-start)/5 << std::endl;
		}
		if (_mode == 1)
		{
			start=clock();
			for(int times = 0 ;times < 100;times++)
			{
				srand((unsigned)time(NULL));
				random_shuffle(_arr.begin(), _arr.end()); 
				for(int j = 0;j<_arr.size() ;j++)
				{
					bst.insert(_arr[j]);
				}
				_arr.clear();
				bst.add(_arr);
			}
			finish=clock();
			std::cout << "The sorting process costs " << (finish-start)/100 << std::endl;
		}
	};
\end{lstlisting}
4.main函数
\begin{lstlisting}
	int main( )
	{
		int testsize;
		int size;
		int mode;
		while (std::cin >> testsize)
		{
			for (int i = 0;i < testsize;i++)
			{
				std::cin >> size >> mode;
				if((mode!=0 && mode !=1) || size <0)
				{
					std::cerr << "Wrong input." << std::endl;
				}
				std::vector<int> arr={};
				for(int i = 0; i< size; i++)
				{
					arr.push_back(i);
				}
				BSTSorting(arr,mode);
			}
			return 0;
		}
	};
\end{lstlisting}
\section{测试说明}
本次测试，我尝试输入10组数据，数组的size为10000,20000，30000,40000,50000,通过每一个size的两种模式测试时间复杂度。\par
通过bash run命令，得到如下测试结果：\par
The sorting process costs 751185\\
The sorting process costs 2945\\
The sorting process costs 3186023\\
The sorting process costs 6317\\
The sorting process costs 7955385\\
The sorting process costs 10379\\
The sorting process costs 15292462\\
The sorting process costs 14273\\
The sorting process costs 25374873\\
The sorting process costs 19495\par
我们知道，mode=0时的时间复杂度约为o($n^2$),而mode=1时的时间复杂度约为o($nlogn$),试验结果表明，时间复杂度基本符合。
同时，执行valgrind bash run命令，检测出程序正常执行时无内存泄漏。\par
==77630== \\
==77630== HEAP SUMMARY:\\
==77630==     in use at exit: 147,882 bytes in 750 blocks\\
==77630==   total heap usage: 925 allocs, 175 frees, 171,300 bytes allocated\\
==77630== \\
==77630== LEAK SUMMARY:\\
==77630==    definitely lost: 0 bytes in 0 blocks\\
==77630==    indirectly lost: 0 bytes in 0 blocks\\
==77630==      possibly lost: 0 bytes in 0 blocks\\
==77630==    still reachable: 147,882 bytes in 750 blocks\\
==77630==         suppressed: 0 bytes in 0 blocks\\
==77630== Rerun with --leak-check=full to see details of leaked memory\\
==77630== \\
==77630== For lists of detected and suppressed errors, rerun with: -s\\
==77630== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)\\

\section{小结}
在测试复杂度时，一次试验会带来许多误差，需要多次试验取平均值才能得到相对较准确的数据。\par
以上就是我在完成这次作业时的思考。

\end{document}
